FIG. 1 depicts a video frame that comprises an image of a person in the prior art. The video frame comprises a two-dimensional array of 720 by 480 8-bit pixels. In some cases, all 345,600 pixels are transmitted when the frame is transmitted, but that requires that 345,600 bytes of data be transmitted for each frame.
There are techniques, however, for reducing, on average, the number of bytes that must be transmitted. One such technique is known as H.264. In accordance with H.264, some of the pixels in a frame are transmitted explicitly while others are not, but instead are derived or extrapolated from those that are.
To accomplish this, the pixels in the video frame are organized in a hierarchy of data structures. First, the frame is partitioned into a two-dimensional array of 45 by 30 macroblocks, as shown in FIG. 2. In turn, and as shown in FIG. 3, each macroblock is partitioned into a two-dimensional array of 4 by 4 luma blocks, and each luma block is partitioned into a two-dimensional array of 8-bit pixels.
All 1350 macroblocks in the frame are established in row-column order, as depicted in FIG. 4, so that each row is established, left to right, before the row before it is established. The 16 luma blocks within each macroblock are established in a specific pattern, as depicted in FIG. 5, to preserve the relationship that each luma block is established only after the luma blocks (if any) above it and to its left have been established. The reason is that the pixels in each luma block are either transmitted explicitly, or they are derived from the pixels in the luma blocks above it and to its left.
The pixels in a luma block are designated p[x,y] through p[x+3, y+3] as depicted in FIG. 6, wherein x ε{x: x=4n} and n ε{n: n is a non-negative integer}; and wherein y ε{y: y=4m} and m ε{m: m is a non-negative integer} (i.e., the values of x and y are restricted to positive multiples of 4). When the pixels in a luma block are predicted based on the pixels above it and to its left, those pixels are designated p[x−1, y−1] through p[x+7, y−1] and p[x−1,y] through p[x−1,y+3], as depicted in FIG. 7. There are a variety of formulas for predicting the pixels in the luma block, as graphically depicted in FIGS. 8a through 8h, but the receiver is not able predict which formula will be used before it is told which formula to use.
This can wreak havoc on the speed with which the video frame can be decoded, and, therefore, the need exists for a technique for ensuring the expedient decoding of a video frame.